package 哈希表系列;

public class CanConstruct {
//    public boolean canConstruct(String ransomNote, String magazine) {
//        int[] arr = new int[26];
//        char ch;
//        for(int i = 0; i < magazine.length();i++){
//            ch = magazine.charAt(i);
//            arr[ch-'a'] ++;
//        }
//        for(int i = 0; i < ransomNote.length();i++){
//            ch = ransomNote.charAt(i);
//            if(arr[ch-'a'] > 0){
//                arr[ch-'a'] --;
//            }else{
//                return false;
//            }
//        }
//        return true;
//    }
    //暴力解法，复杂度为n^2，这里是C++解法
//    public boolean canConstruct(String ransomNote, String magazine) {
//        //记录杂志字符串出现的次数
//        for (int i = 0; i < magazine.length(); i++) {
//            for (int j = 0; j < ransomNote.length(); j++) {
//                // 在ransomNote中找到和magazine相同的字符
//                if (magazine[i] == ransomNote[j]) {
//                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
//                    break;
//                }
//            }
//        }
//        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
//        if (ransomNote.length() == 0) {
//            return true;
//        }
//        return false;
//    }
    //标准解法
    public boolean canConstruct(String ransomNote, String magazine) {
        //记录杂志字符串出现的次数
        int[] arr = new int[26];
        int temp;
        for (int i = 0; i < magazine.length(); i++) {
            temp = magazine.charAt(i) - 'a';
            arr[temp]++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            temp = ransomNote.charAt(i) - 'a';
            //对于金信中的每一个字符都在数组中查找
            //找到相应位减一，否则找不到返回false
            if (arr[temp] > 0) {
                arr[temp]--;
            } else {
                return false;
            }
        }
        return true;
    }
}
